package sublinear.algorithm;

import java.util.ArrayDeque;
import java.util.Collection;
import java.util.HashMap;
//import java.util.HashSet;
import java.util.Iterator;
import java.util.logging.Logger;

import sublinear.common.SimplePRNG;
import sublinear.model.AbstractGraph;
import sublinear.model.AbstractGraph.GraphNode;

public class ApproximationAlgorithms {
	
	private static final Logger log = Logger.getLogger( ApproximationAlgorithms.class.getName() );
	
	// takes random sample of nodes 
	private static GraphNode[] takeRandomSampleOfNodes(AbstractGraph G, int N) {
		
		log.info("Taking random sample of size " + N);
		
		GraphNode[] S = new GraphNode[N];
		for (int i=0; i<N; i++){
			GraphNode v = S[i] = G.getRandomNode();
			v.setDegree((int) G.getDegree(v));
			log.finest("Added " + v.getFriendlyName() + " (" + v.getUniqueId() + ") to sample. Degree: " + v.getDegree());
		}
		
		log.info("Done taking sample of size " + N);
		
		return S;
	}
	
	public static int approximateAverageDegree(AbstractGraph G, double C, double epsilon){
		
		int D = 0;
		int N = (int) (C/epsilon);
		
		log.info("Approximating average degree. Using " + N + " sized sample for approximation");
		
		GraphNode[] S = takeRandomSampleOfNodes(G,N);
		for (int i=0; i<N; i++){
			GraphNode v = S[i];
			int d = (int) G.getDegree(v);
			if (d > D){
				D = d;
			}
		}
		
		log.info("Approximated average degree for the graph: " + D);
		
		return D;
		
	}
	
	public static int getMaxDegree(AbstractGraph G, Collection<GraphNode> nodes){
		
		int D = 0;
		Iterator<GraphNode> itr = nodes.iterator();
		while (itr.hasNext()){
			GraphNode v = itr.next();
			int d = (int) G.getDegree(v);
			if (d > D){
				D = d;
			}

		}
		return D;
	}
	
	
	/**
	 * Sublinear time method for approximating the number of connected components in the given graph
	 * 
	 * @param G Graph object
	 * @param C Algorithm constant
	 * @param epsilon The Epsilon parameter should be a small value within [0..1]. 
	 * Gives trade-off between speed and accuracy (smaller value gives more accuracy and more work)  
	 * @param W Max nodes to search within each random start location 
	 * @param n Graph size
	 * @param maxDegree Max degree of the graph (can be approximated as well)
	 * @return Approximated number of connected components
	 */
	public static double approximateConnectedComponents(AbstractGraph G, double C, double epsilon, long W, long n, int maxDegree)
	{
		//initialize local variables
		SimplePRNG coin = SimplePRNG.getInstance();
		int r = (int) (C/(epsilon*epsilon));
		
		GraphNode[] S = takeRandomSampleOfNodes(G,r);
		double[] betas = new double[r];
		
		log.info("Approximating number of connected components. Sample size: " + r + " max nodes in component to visit: " + W 
				+ " graph size: " + n + " average degree: " + maxDegree);

		ArrayDeque<GraphNode> bfsQueue = new ArrayDeque<GraphNode>();
		HashMap<Long,GraphNode> visitedIds = new HashMap<Long,GraphNode>();
		
		for (int i=0; i<r; i++){
			GraphNode u = S[i];
			// Must reset it here
			u.setNumEdges(0);
			bfsQueue.clear();
			visitedIds.clear();

			long visitedNodes = GraphSearch.breadthFirstSearch(G, u, W, bfsQueue, visitedIds);
			int maxDegVisited = getMaxDegree(G, visitedIds.values());
			
			int numFlips = 0;
			while(coin.flipUnbiasedCoin()==1 && visitedNodes < W && !(maxDegVisited > maxDegree)){
				numFlips++;
				
				visitedNodes = GraphSearch.breadthFirstSearch(G, u, W, bfsQueue, visitedIds);
				maxDegVisited = getMaxDegree(G, visitedIds.values());
				
				if (visitedNodes < W){ //BFS is complete
					if (u.getNumEdges()==0){
						betas[i] = 2;
					} else{
						betas[i]=u.getDegree()*Math.pow(2, numFlips)/u.getNumEdges();
					}
					break;
				}
			}
		}
		double estimate = 0;
		for (int i=0; i<r; i++){
			estimate+=betas[i];
		}
		return (n/(2*r))*estimate;
	}
	
}
